#ifndef __BASIC_MAPEX_H__
#define __BASIC_MAPEX_H__

#include <map>

template <typename K, typename T>
class mapex final {
private:
  struct _Linkage {
    T value = nullptr;
    _Linkage* _next = nullptr;
    _Linkage* _previous = nullptr;
    void ClearLinkages() {
      _next = nullptr;
      _previous = nullptr;
    }
  };

public:
  mapex(const mapex&) = delete;
  const mapex& operator=(const mapex&) = delete;
  mapex() : m_rootLinkage(new _Linkage()) {
    m_lastLinkage = m_rootLinkage;
  }
  ~mapex() {
    m_map.clear();
    _Linkage* pTmp = m_rootLinkage;
    if (pTmp) {
      _Linkage* tmp = pTmp;
      pTmp = pTmp->_next;
      delete tmp;
    }
    m_rootLinkage = nullptr;
    m_currentLinkage = nullptr;
  };

public:
  void Set(K key, T value) {
    _Linkage* pTmp = _Get(key);
    if (!pTmp) {
      pTmp = new _Linkage();
      m_map[key] = pTmp;
    }
    pTmp->value = value;
    m_lastLinkage->_next = pTmp;
    pTmp->_previous = m_lastLinkage;
    m_lastLinkage = pTmp;
  };

  T Get(K key) {
    _Linkage* pTmp = _Get(key);
    return pTmp ? pTmp->value : nullptr;
  };

  T Remove(K key) {
    _Linkage* pTmp = _Remove(key);
    if (pTmp) {
      _Remove(pTmp);
      T r = pTmp->value;
      delete pTmp;
      return r;
    } else
      return nullptr;
  };

  T GetFirst() {
    m_currentLinkage = m_rootLinkage->_next;
    return m_currentLinkage ? m_currentLinkage->value : nullptr;
  };

  T GetNext() {
    m_currentLinkage = m_currentLinkage->_next;
    return m_currentLinkage ? m_currentLinkage->value : nullptr;
  };

private:
  void _InsertToNext(_Linkage* target, _Linkage* des) {
    _Linkage* pNext = des->_next;
    des->_next = target;
    target->_next = pNext;
    pNext->_previous = target;
    target->_previous = des;
  }

  void _Remove(_Linkage* target) {
    if (target == m_currentLinkage) {
      m_currentLinkage = m_currentLinkage->_previous;
    }
    if (target == m_lastLinkage) {
      m_lastLinkage = m_lastLinkage->_previous;
    }
    _Linkage* pNext = target->_next;
    _Linkage* pPrevious = target->_previous;
    pPrevious->_next = pNext;
    if (pNext) {
      pNext->_previous = pPrevious;
    }
    target->ClearLinkages();
  }

  _Linkage* _Remove(K key) {
    auto it = m_map.find(key);
    if (it == m_map.end())
      return nullptr;
    else {
      _Linkage* r = it->second;
      m_map.erase(it);
      return r;
    }
  };

  _Linkage* _Get(K key) {
    auto it = m_map.find(key);
    if (it == m_map.end())
      return nullptr;
    return m_map[key];
  };

private:
  std::map<K, _Linkage*> m_map;
  _Linkage* m_rootLinkage = nullptr;
  _Linkage* m_lastLinkage = nullptr;
  _Linkage* m_currentLinkage = nullptr;
};

#endif
